package labuladong

/**
 * @Description: 104. 二叉树的最大深度 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/20 22:14
 **/
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var left = 1 + maxDepth(root.Left)
	var right = 1 + maxDepth(root.Right)
	if left > right {
		return left
	}
	return right
}

/**
 * @Description: 144. 二叉树的前序遍历 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/20 22:19
 **/
func preorderTraversal(root *TreeNode) []int {
	var res []int
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val)
		dfs(node.Left)
		dfs(node.Right)
	}

	dfs(root)
	return res
}

/**
 * @Description: 543. 二叉树的直径 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/20 22:21
 **/
func diameterOfBinaryTree(root *TreeNode) int {
	var max int
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node.Left == nil && node.Right == nil {
			return 0
		}
		var left int
		if node.Left != nil {
			left = dfs(node.Left) + 1
		}
		var right int
		if node.Right != nil {
			right = dfs(node.Right) + 1
		}
		if left+right > max {
			max = left + right
		}
		if left > right {
			return left
		}
		return right
	}

	dfs(root)
	return max
}
